package com.leetcode.practice.leetcode;

/**
 * 363.矩形区域不超过 K 的最大数值和
 */
public class No363 {

    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {64,48,10,39,72,77,87,55,78,70,10,73,54,12,53,30,55,44,25,43,72,90,22,64,52,75,47,82,61,84,97,20,17,72,41,58,62,65,20,47,82,22,27,83,65,43,3,16,69,28,43,35,67,71,52,29,93,69,73,39,76,64,92,86,15,98,47,47,56,9,26,51,2,1,68,21,38,9,61,28,34,46,44,35,63,21,97,98,14,68,92,8,34,10,46,22,20,62,44,73},
                {84,71,84,58,1,53,78,60,7,82,56,96,69,35,2,46,10,25,81,24,58,14,57,9,63,50,2,98,50,59,2,50,51,94,46,34,44,21,7,57,56,1,55,61,40,40,12,63,93,27,60,3,29,62,75,59,67,11,93,8,93,36,72,90,97,56,76,50,65,8,64,37,55,46,93,95,32,42,8,96,40,95,1,1,11,69,12,71,94,61,88,4,52,81,3,2,90,77,0,21},
                {65,53,72,87,51,68,33,50,52,37,69,73,46,80,78,11,47,67,94,5,54,98,17,17,71,84,21,15,95,39,53,71,72,26,5,83,61,77,85,95,17,53,85,67,40,9,17,36,22,56,68,49,15,60,45,91,7,55,49,11,88,4,67,12,25,33,10,46,44,23,48,17,22,25,31,80,50,29,76,76,11,91,27,48,66,96,93,63,24,51,18,53,96,46,74,93,28,23,0,-1}};
        System.out.println(new No363().maxSumSubmatrix(matrix,-1));
    }

    public int maxSumSubmatrix(int[][] matrix, int k) {
        //前缀二分统计法
        return practiceFirst(matrix,k);
    }

    /**
     * 记录所有组合类型的值，简单二分法遍历
     * @param matrix
     * @param k
     * @return
     */
    private int practiceFirst(int[][] matrix, int k) {
        int column = matrix.length;
        int row = matrix[0].length;
        int[][] sums = new int[column + 1][row + 1];
        int max=Integer.MIN_VALUE,current=Integer.MIN_VALUE;

        for (int i = 1; i <= column; i++) {
            for (int r = 1; r <= row; r++) {
                //记录原点（0,0）到各个位置的数据总和
                sums[i][r] = sums[i - 1][r] + sums[i][r - 1] - sums[i - 1][r - 1] + matrix[i - 1][r - 1];
            }
        }

        for (int left = 1; left <= row; left++) {
            for (int right = left; right <= row; right++) {
                //将区间内的行总数累加遍历
                for (int i = 1; i <= column; i++) {
                    for(int j = i; j <= column; j++){
                        if(i == 1){
                            current = sums[j][right] - sums[j][left - 1];
                        }else{
                            current = sums[j][right] - sums[j][left - 1] - sums[i - 1][right] + sums[i - 1][left - 1];
                        }
                        if(current <= k && current > max){
                            max = current;
                        }
                    }
                }

            }
        }

        return max;
    }

}
